class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def delete(self, data):
        if self.head is None:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

    def search(self, data):
        current = self.head
        index = 0
        while current:
            if current.data == data:
                return index
            current = current.next
            index += 1
        return -1

    def reverse(self):
        prev = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" ")
            current = current.next
        print()
    def rearrange_oddeven(self):
        if self.head is None or self.head.next is None:
            return

        odd_head = None
        odd_tail = None
        even_head = None
        even_tail = None

        current = self.head

        while current is not None:
            if current.data % 2 == 0:  # 当前节点的值为偶数
                if even_head is None:
                    even_head = current
                    even_tail = current
                else:
                    even_tail.next = current
                    even_tail = even_tail.next
            else:  # 当前节点的值为奇数
                if odd_head is None:
                    odd_head = current
                    odd_tail = current
                else:
                    odd_tail.next = current
                    odd_tail = odd_tail.next

            current = current.next

        if odd_head is None:  # 没有奇数节点
            self.head = even_head
        else:
            self.head = odd_head
            odd_tail.next = even_head

        if even_tail is not None:  # 结束偶数节点链表
            even_tail.next = None



# 测试代码

linked_list_xzc = LinkedList()
n = int(input("请输入链表元素个数："))
for i in range(n):
    data = int(input("请输入第{}个元素的值：".format(i+1)))
    linked_list_xzc.insert(data)

print("链表中的元素：")
linked_list_xzc.display()

delete_data = int(input("请输入要删除的元素的值："))
linked_list_xzc.delete(delete_data)

print("删除元素后的链表：")
linked_list_xzc.display()

search_data = int(input("请输入要查找的元素的值："))
index = linked_list_xzc.search(search_data)
if index != -1:
     print("元素{}的序号为：{}".format(search_data, index))
else:
    print("未找到元素{}。".format(search_data))

print("链表中当前的元素：")
linked_list_xzc.display()
linked_list_xzc.reverse()
print("链表逆序后的元素排列：")
linked_list_xzc.display()
linked_list_xzc.rearrange_oddeven()

print("Modified Linked List:")
linked_list_xzc.display_list()
